A navigation device has road map data indicating road connections. The road connections can be expressed using link data and node data.
The link data includes, with respect to a link, characteristic data such as a link ID identifying the link, coordinates of both ends of the link (road), a road type, a road length, and a road width. The node data includes, with respect to a node, characteristic data such as a node ID identifying the node, link IDs of links connected with the node, and a node type (e.g., intersection, fork, junction). In this road map data, road connections are expressed by assigning link IDs to node data.
Other than navigation devices, the following devices have road map data: a device for managing road map data by dividing all area into divisional regions, a device for updating road map data with respect to each of the divisional regions, and a device for updating road map data with respect to each link. (See Patent Documents 1 to 4)                Patent Document 1: JP-3391171 B2        Patent Document 2: JP-2004-178248 A        Patent Document 3: JP-2004-294599 A        Patent Document 4: JP-2004-354268 A        
When the road map data is divided depending on each divisional region, updating the road map data can be made without need of updating the road map data corresponding to all the area. This simplifies update of the road map data. In this case, a road connection is expressed such that a link ID or node ID of a connecting end in a certain divisional region is directly associated with a link ID or node ID of a connected end in a neighboring divisional region. Therefore, when a link ID or node ID in the certain divisional region is changed and the road map data in the certain divisional region is thereby updated, the road map data in the neighboring divisional region needs to be updated simultaneously.
For instance, in Patent Document 1, border nodes have connection information of neighboring divisional regions. When a node ID or link ID is changed and road map data is updated (see FIG. 13), the connection information of the border nodes needs to be updated.
With reference to FIG. 14, the detailed explanation will be added below. As shown in map data D′11 and D′21 in FIG. 14, the border node of ID “N21” in a first divisional region has connection information indicating link ID “L11” as a connected link in a second divisional region next to the first divisional region. The connected link is then changed from the link of ID “L11” to the link of ID “L12” due to a new road construction in the second divisional region, as shown in map data D′22 in FIG. 14.
This breaks off the road connection between the border node of “N21” and the connected link of “L11.” Accordingly, to maintain the road connection, the road map data D′11 needs to be updated to change the connected link ID from “L11” to “L12,” as shown in map data D′12 in FIG. 14.
A certain update method may be proposed that update of road map data be executed not to involve change of a link ID or node ID connecting to a border. However, this results in discontinuous assignment of IDs by disregarding practical geographical arrangement of nodes and links. Therefore, efficiency in retrieval of information within the road map data is degraded. In other words, when the retrieval efficiency is prioritized, assignment of IDs needs to meet retrieval algorithm. As a result, the above certain method poses the problem in information retrieval.
Further, another method may be proposed that, to prevent road map data update only for changing connection information, connection data be prepared independently from the road map data in each divisional region as shown in D′41 in FIG. 15A. With respect to the node of ID “N21” in a first divisional region (see D′31 in FIG. 15A), suppose the case where a connected link in a second divisional region is changed from the link of ID “L11” to the link of ID “L12” (i.e., D′51 is updated to D′52). In this case, the connection data D′41 between the node of ID “N21” and the link of ID “L11” is updated to D′42 without need to update the road map data D′31.
Preparing the above connection data may apply to a system for updating road map data of each divisional region. In this system, each of multiple combinations of road map data versions of neighboring divisional regions requires corresponding connection data, which complicates works for data generation.
For instance, road map data having versions 1 to N (N: positive integer) requires N×N version combinations between two neighboring divisional regions. FIG. 15B illustrates an example of combinations in case of N equal to three. As a result, in the system to change road map data with respect to each divisional region, the above method requires a data provider to prepare connection data items equal to the square of the number of versions.